package permute46;

import java.util.ArrayList;
import java.util.List;

public class Permute {

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        dfs(nums,lists,new ArrayList<>());
        return lists;
    }

    //主要思路：深度优先遍历
    public void dfs(int[] nums,List<List<Integer>> lists,List<Integer> list){
        //终止条件，当递归放入list的个数等于数组的个数说明被选择完了
        if(list.size() == nums.length){
            lists.add(new ArrayList<>(list));
            return;
        }
        //https://gitee.com/z_lamber/image-bed/raw/master/20210930171032.png
        for (int i = 0; i < nums.length; i++) {
            //一次遍历一个数只能获取一次
            if(list.contains(nums[i])){
                continue;
            }
            list.add(nums[i]);
            //开始递归
            dfs(nums,lists,list);
            //回归后需要将list中放入的值删除
            list.remove(list.size() - 1);

        }

    }


    public static void main(String[] args) {
        int[] a = {1, 2, 3};
        Permute permute = new Permute();
        System.out.println(permute.permute(a));

    }

}
